The present invention relates to a route search method, used for scheduling or distribution fields, that employs time windows to increase the speed of execution of an algorithm employed for a routing problem.
The routing problem in this specification involves calculations used to determine in what order a truck, which departs from and returns to an initial location, must arrive at a number of intervening transit points to ensure that the least time is spent on the road (the required time) and the least (shortest) distance is traveled. A further, included problem is one wherein multiple trucks are scheduled to visit a set of transit points. For routing problems for which xe2x80x9ctime windowsxe2x80x9d are used, time restrictions are imposed. For example, specific times are set for a truck to depart from and return to an initial location, while for each intervening transit point visited en route, a time range is established for the arrival of the truck, with a late arrival being regarded as a delay. In FIG. 1, for example, the time restriction imposed provides for the arrival at a transit point Px within a time range, illustrated by the hard time window in prior art FIG. 2, extending from 10:30 to 11:45. In FIG. 2, the initial sets EST (Earliest Start Time) and LST (Latest Start Time) represent a static earliest arrival time and a static latest arrival time established for a specified transit point. Costs outside the time window become infinite.
In addition, the total weight or number of products to be delivered to transit points must not exceed the loading capacity of a truck. This is a problem, for one truck, called the TSPTW (Traveling Salesman Problem with Time Windows) or the VRPTW (Vehicle Routing Problem with Time Windows). One of the VRPTWs that appear in a scheduling field (job shop scheduling) is a problem, involving the determination of the order in which jobs are to be processed by a machine, for which preparation time between jobs is especially required. In this case, a truck corresponds to a machine, and a transit point corresponds to a job. Each job must be processed following the time whereat the process at a preceding step is terminated, and must be transferred to a succeeding step before a deadline is reached. When a required time (called xe2x80x9cmake spanxe2x80x9d) is reduced by satisfying such a restriction, the operating ratio for the machine can be improved. For a scheduling field, the number of transit points is frequently equal to or greater than 10,000, and a great demand exists for a scaleable algorithm.
As the algorithm used for the above problem, a local search method is generally employed. That is, an operation is repeated whereby a xe2x80x9cpart of a route after departing a specific solution is moved to another portion, and when the length of the route is reduced, that movement is employedxe2x80x9d. The following example shows an operation performed to move the location of a specific transit point and an operation for exchanging two transit points. An operation for moving or exchanging continuous transit points (paths) is also generally employed. The location or locations to be moved or exchanged may be either along a route or between different routes. Changes effected for transit points are shown in FIGS. 3A and 3B. In FIG. 3A, a transit point X is moved from the right route to the left route, and in FIG. 3B, a transit point X, along the right route, is exchanged with a transit point Y, along the left route.
The time required for the execution of the algorithm for this problem is determined mainly by the following two factors.
(a) The procedures required for route evaluation when a part of a route is moved to another location.
(b) The number of trials required when moving a part of a route to another location.
The method that could most easily be used for (a) is probably one that provides for the evaluation of a route by traveling it (while calculating the required time). According to this method, however, O(n) procedures are required when the number of transit points is defined as n. As for (b), at least n trials will be required, and the general trend will be for the problem size to be empirically increased until it is close to O(square of n). Therefore, when the procedures required for the first method are multiplied by O(n), the algorithm is at least O(square of n), or is empirically increased close to O(cube of n), so that scalability of a large problem is not possible.
It is, therefore, one object of the present invention to reduce the time required for route evaluation when in the routing problem one part of a route is moved to another location, and to ensure scalability of even a large problem.
The aim of the present invention is the implementation of the following points.
(a) The employment of a penalty function that can be added.
(b) The addition of penalty functions for all succeeding transit points following transit points along a route, and the storage of the results at the pertinent transit points.
(c) The efficient examination of whether the addition time information for each transit point is valid. In this invention, by implementing these points, the time required for route evaluation can be limited substantially to a constant time.